The present invention relates to a method and apparatus for automatically partitioning a circuit in circuit design for LSI.
As a conventional method of partitioning a circuit in circuit design for LSI, there has been known one discussed in the 179th to 210th sections of "HIGH-LEVEL SYNTHESIS" written by Daniel Gajski, Nikil Dutt, Allen Wu, and Steve Lin, in which initial partitioning of a circuit is followed by temporary movement of one or more circuit elements from one block to another and calculation of the number of nets connecting the blocks to each other. The method enables to improve initial partitioning by actually performing such movement as to minimize the number of nets connecting the blocks. The term "net" is defined here as a signal line connecting elements or terminals to be logically connected.
To minimize the value given by (Number of Edges Contained in Cluster)--(Number of Edges Extending Outwardly from Cluster), the conventional method of initial partitioning also performs repeated clustering with respect to nodes and cuts a clustering tree generated by repeated clustering.
However, the conventional method of partitioning a circuit has the problem of longer processing time due to a large number of combinations formed by the circuit elements to be temporarily moved. Moreover, since the processing time cannot be estimated in advance, and the processing time and the result of execution are contradictory to each other, it is difficult to provide a satisfactory compromise between the processing time and the result of execution.
Additionally, the conventional method of partitioning a circuit also has the problem of great difference among block sizes.
To partition a graph consisting of six nodes shown in FIG. 28 into three blocks, e.g., initial clustering is performed with respect to the first and second nodes n201 and n202 to generate a cluster c210 as shown in FIG. 29(a). Then, as shown in FIGS. 29(b) to 2(d), the third, fourth, fifth, and sixth nodes n203, n204, n205, and n206 are sequentially clustered to be assigned to the cluster c210, thereby generating the clustering tree shown in FIG. 30(a). The graph is partitioned into three blocks as shown in FIG. 30(b) by cutting the clustering tree at the portions indicated by the two dash-dot lines. However, although the block 1 contains four nodes therein, each of the blocks 2 and 3 contains only one node therein.